package LeetCodeHot100TopInterview;

import java.util.HashMap;

public class Q146_LRUCache {


    //LRU封装的信息 ==> 本质上是双向链表节点
    class LRUNode<K,V>{
        //节点 key
        private K key;
        //节点 value
        private V value;
        //上一个节点
        LRUNode<K,V> last;
        //下一个节点
        LRUNode<K,V> next;

        public LRUNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    //双向链表 头到尾 ==> 未被使用的时间越来越短 ==> 头部就是最少使用的
    class DoubleLinkedList {
        //头节点
        LRUNode<Integer,Integer> head;
        //尾节点
        LRUNode<Integer,Integer> tail;
        //添加链表到双向链表 ==> 添加到尾部
        public void addNode(LRUNode<Integer,Integer> node){
            if (node == null){
                return;
            }
            //没数据,直接放
            if (head == null){
                head = node;
                tail = node;
            }else {
                //有数据,添加到尾部
                tail.next = node;
                node.last = tail;
                tail = node;
            }
        }

        //添加节点到尾部 ==> 代表最近被使用
        //参数节点必定是存在于链表中的
        //容量在上层判断
        public void moveToTail(LRUNode<Integer,Integer> node){
            //如果是尾节点 啥也不用干 || 前面控制 节点数量为一的情况 不用进来
            if (node == tail){
                return;
            }
            //如果是头节点
            if (node == head){
                //换个头再操作
                head = head.next; //null?
                head.last = null;
            }else {
                //中间任意节点
                node.last.next = node.next;
                node.next.last = node.last;
                //此时 node 就是孤魂野鬼了 只留下两条指向前后的指针
                //node.last = null;
            }
            //有数据,添加到尾部
            node.last = tail;
            node.next = null;
            tail.next = node;
            tail = node;
        }

        //淘汰最近最久未被使用的节点
        //此时直接换头
        public LRUNode<Integer,Integer> removeHead(){
            if (head == null){
                return null;
            }
            LRUNode<Integer,Integer> ans = head;
            if (head == tail){
                head = null; //注意: 此时 head 指针指向 null head 原生指向的空间被 ans 接管
                tail = null;
                return ans;
            }
            this.head = head.next;
            //指向原先头的指针废掉  保证头节点没有被引用指到
            ans.next = null;
            head.last = null;
            return ans;
        }
    }

    //LRU Cathe
    DoubleLinkedList queue;
    //真正存数据的地方
    HashMap<Integer,LRUNode<Integer,Integer>> map;
    //容量
    final private int capacity;

    public Q146_LRUCache(int capacity) {
        this.capacity = capacity;
        queue = new DoubleLinkedList();
        map = new HashMap<>();
    }

    //
    public int get(int key) {
        if (map.containsKey(key)){
            Integer ans = map.get(key).value;
            //被使用了 移动到尾部
            if (map.size() == 1) {
                return ans;
            }
            this.queue.moveToTail(map.get(key));
            return ans;
        }
        return -1;
    }

    //可能是更新、可能是新增
    public void put(int key, int value) {
        //更新
        if (map.containsKey(key)){
            map.get(key).value = value;
            this.queue.moveToTail(map.get(key));
            return;
        }
        //新增
        //满员 ==> 淘汰
        if (map.size() == capacity){
            LRUNode<Integer, Integer> head = this.queue.removeHead();
            //map 删除
            this.map.remove(head.key);

        }
        //
        LRUNode<Integer, Integer> newNode = new LRUNode<>(key, value);
        this.map.put(key, newNode);
        this.queue.addNode(newNode);
    }

    public static void main(String[] args) {
        Q146_LRUCache cache = new Q146_LRUCache(2);
        cache.put(1,1);
        cache.put(2,2);
        System.out.println(cache.get(1));
        cache.put(3,3);
        System.out.println(cache.get(2));
        cache.put(4,4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }

}
